package com.algorithm.排序.基于比较的排序;

import com.algorithm.排序.Sort;

public class 插入排序3_二分搜索挪动<E extends Comparable<E>> extends Sort<E> {
/*    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            E v = array[begin];
            int insertIndex = search(begin);
            //将 [insertIndex, begin] 范围内的元素往右边挪动一个单位
            for (int i = begin ; i > insertIndex ; i--) {
                array[i] = array[i - 1] ;
            }
            array[insertIndex] = v;
        }
    }*/

    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            insert(begin, search(begin));
        }
    }

    /**
     * 将source位置的元素插入到dest位置
     * @param source
     * @param dext
     */
    private void insert(int source, int dext) {
        E v = array[source];
        for (int i = source; i < dext ; i--) {
            array[i] = array[i - 1];
        }
        array[dext] = v;
    }

    /**
     * 利用二分搜索找到index位置元素的待插入位置
     */
    private int search(int index) {
        int begin = 0 ;
        int end = index;

        while (begin < end){
            int mid = (begin + end) >> 1;
            if (cmp(array[index],array[mid]) < 0){
                end = mid;
            }else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}